package com.nanbei.backyracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @ClassDescription: 数组中和 leetCode40
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/12 17:03
 */
public class CombinationSumIi {

    public static void main(String[] args) {
        List<List<Integer>> combine = combinationSum2(new int[]{10,1,2,7,6,1,5}, 8);
        System.out.println(combine);
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {

        // 用来判断是否访问标识
        boolean[] visited = new boolean[candidates.length];
        List<List<Integer>> coll = new ArrayList<>();
        LinkedList<Integer> stack = new LinkedList<>();
        Arrays.sort(candidates);
        sf(coll, stack, candidates, 0, target,0,visited);
        return coll.stream().distinct().collect(Collectors.toCollection(ArrayList::new));
    }

    private static void sf(List<List<Integer>> coll, LinkedList<Integer> stack, int[] candidates, int index, int target, int sum, boolean[] visited) {
        // 当栈中的元素数量等于数组长度时，表示找到了一种排列

        if (sum == target) {
            coll.add(new ArrayList<>(stack));
            return;
        }


        for (int i = index; i < candidates.length; i++) {


            //减枝操作
            if (target-sum  < candidates[i]  ){
                continue;
            }
            if (i>0 && !visited[i-1] && candidates[i-1] == candidates[i]){
                continue;
            }

            // 将该数字加入栈中
            visited[i] = true;
            stack.push(candidates[i]);
            sum +=candidates[i];
            // 递归调用后面的数字
            sf(coll,stack,candidates,i+1,target,sum, visited);
            // 回溯：将该数字移出栈
            sum-=candidates[i];
            stack.pop();
            visited[i] = false;


        }

    }


    /*public static List<List<Integer>> combinationSumIi(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> coll = new ArrayList<>();
        LinkedList<Integer> stack = new LinkedList<>();

        for (int i = 0; i < candidates.length; i++) {
            int sum = 0;
            int num = candidates[i];

            if (num == target){
                coll.add(new ArrayList<>().add(sum));
            }

            if (num < target){
                sum = num;
                stack.push(num);
            }

            for (int j = i; j < candidates.length; j++) {

            }
        }
    }*/
}
